% !TEX root = ../ICDM2011.tex
% 
\begin{algorithm}[H]
\caption{ \textbf{A}daptive \textbf{T}ransfer \textbf{C}lustering (\ALG) }
 \label{alg:1}
\begin{algorithmic}[1]
\REQUIRE{$\mathcal{X}_{T}$: target item set; 
$\mathcal{Y}_{T}$: target cluster space;
$\mathcal{X}_{S}$: auxiliary item set; 
$\mathcal{Y}_{S}$: auxiliary cluster space;
$\mathcal{F}$: common feature set;
$\mathcal{Y}_{F}$: feature cluster space;
initial clustering functions $h_T^{(0)}, h_S^{(0)} \text{and } h_F^{(0)}$;
$iter$: the number of iterations.}
\ENSURE{$h_T^{(iter)}$: the final clustering function on $\mathcal{X}_{T}$.}



%\STATE Translate the feature space of target domain $\mathcal{X}_{T}$ into \\the source domain: $\mathcal{X}_{T}^{T} = T(\mathcal{X}_{T})$;

\STATE Initialize $p(\mathcal{F}|\mathsf{x}_{t})$, $q(\mathcal{F}|\mathsf{x}_{s})$, $p(\mathcal{X}_T|f)$ and $q(\mathcal{X}_S|f)$ based on the observations on $\mathcal{X}_{T}$, $\mathcal{X}_{S}$ and $\mathcal{F}$;

\STATE Initialize $\lambda_f$ using Eq.~(\ref{eq13});

\STATE Initialize $\tilde{p}^{(0)}(\mathcal{F}|\mathsf{y}_{t})$, $\tilde{q}^{(0)}(\mathcal{F}|\mathsf{y}_{s})$, $\tilde{p}^{(0)}(\mathcal{X}_T|\mathsf{y}_{f})$ and $\tilde{q}^{(0)}(\mathcal{X}_S|\mathsf{y}_{f})$ based on $h_{T}^{(0)}$, $h_{S}^{(0)}$, $h_{F}^{(0)}$ and the observations on $\mathcal{X}_{T}$, $\mathcal{X}_{S}$ and $\mathcal{F}$;

\STATE Initialize  $w_{tf}^{(0)}$ and $w_{sf}^{(0)}$ using Eq. ~(\ref{eq15}) and Eq. ~(\ref{eq17});

\FOR{$t\leftarrow1,\ldots,iter$}
	\STATE Update $h_T^{(t)}$ based on $p(\mathcal{F}|\mathsf{x}_{t})$, $\tilde{p}^{(t-1)}(\mathcal{F}|\mathsf{y}_{t})$ and $w_{tf}^{(t-1)}$ using Eq.~(\ref{eq14});
	\STATE Update $h_S^{(t)}$ based on $q(\mathcal{F}|\mathsf{x}_{s})$, $\tilde{q}^{(t-1)}(\mathcal{F}|\mathsf{y}_{s})$ and $w_{sf}^{(t-1)}$  using Eq.~(\ref{eq16});
	\STATE Update $h_F^{(t)}$ based on $p(\mathcal{X}_T|f)$, $q(\mathcal{X}_S|f)$, $\tilde{p}^{(t-1)}(\mathcal{X}_T|\mathsf{y}_{f})$, $\tilde{q}^{(t-1)}(\mathcal{X}_S|\mathsf{y}_{f})$ and $\lambda_f$ using Eq.~(\ref{eq11});
           \STATE Update $w_{tf}^{(t)}$ and $w_{sf}^{(t)}$ using Eq. ~(\ref{eq15}) and Eq. ~(\ref{eq17});
\ENDFOR


\RETURN $h_T^{(iter)}$ as the final clustering function on target item set $\mathcal{X}_T$
\end{algorithmic}
\end{algorithm}

\comment{
\begin{lemma}\label{lemma1}
In Algorithm 1, let the value of objective function $\mathcal{J}$ in the t-th iteration be
\begin{equation}\label{le1}
\begin{split}
\mathcal{J}^{(t)}=&D_W(p(\mathcal{X}_{T},\mathcal{F})\|\tilde p^{(t)}(\mathcal{X}_{T},\mathcal{F}))\\
&+\lambda D_W(q(\mathcal{X}_{S},\mathcal{F})\|\tilde q^{(t)}(\mathcal{X}_{S},\mathcal{F})).
\end{split}
\end{equation}
Then, we have
\begin{equation}\label{le2}
\mathcal{J}^{(t)}>\mathcal{J}^{(t+1)}
\end{equation}
\end{lemma}
\begin{proof}
(Sketch) Since in each iteration, update is made based on Eqs.~(\ref{eq11}), (\ref{eq14}) and (\ref{eq16}) to locally minimize the value of $D_W(p(\mathcal{X}_{T},\mathcal{F})\|\tilde p^{(t)}(\mathcal{X}_{T},\mathcal{F}))$ and $D_W(q(\mathcal{X}_{S},\mathcal{F})\|\tilde q^{(t)}(\mathcal{X}_{S},\mathcal{F}))$, we can easily have Lemma~\ref{lemma1} as the consequence.
\end{proof}

\begin{theorem}
Algorithm 1 converges in a finite number of iteration times.
\end{theorem}
\begin{proof}
(Sketch) Based on the fitness of solution space and the decreasing property illustrated in Lemma~\ref{lemma1}, the convergence of our algorithm \ALG\ can be proved directly.
\end{proof}
}
\subsection{Complexity Analysis}
In this section, we theoretically analyze the computational costs of our algorithm \ALG. Suppose that the total number of co-occurrences of pair $(\mathsf{x},f)$ is $N$ in target set. Similarly, the number of pair $(\mathsf{x},f)$ co-occurrences is $M$ in auxiliary set. Thus, in each iteration, updating $h_{T}$ takes $\Theta(C_T\cdot N)$ while freshing $h_S$ requires $\Theta(C_S\cdot M)$. Meanwhile, modifying $h_F$ consumes $\Theta(C_\mathcal{F}\cdot(N+M))$. Given the iteration times $iter$, the time complexity of out algorithm \ALG\ is $\Theta(iter\cdot(N\cdot(C_T+C_\mathcal{F})+M\cdot(C_S+C_\mathcal{F})))$. In the following experiments, we show that our algorithm usually converges within 20 iteration times. Generally, $C_T$, $C_S$ and $C_\mathcal{F}$ are considered as constraints, so that \ALG\ runs in linear time $\Theta(M+N)$.

As to space complexity, our algorithm \ALG\ needs to store all the pairs of $(\mathsf{x},f)$ and their corresponding probabilities. Hence, the space complexity is $\Theta(M+N)$ too. This reveals that our algorithm \ALG\ runs linearly in terms of both time and space. We may draw a conclusion that our algorithm \ALG\ has good scalability.
%\vspace{-0.1in}